package com.ly.algorithm.leetcode.binarysearch;

/**
 * @Classname Problem74
 * @Description
 *
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 *
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 *  
 *
 * 示例 1：
 *
 *
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
 * 输出：true
 * 示例 2：
 *
 *
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
 * 输出：false
 * 示例 3：
 *
 * 输入：matrix = [], target = 0
 * 输出：false
 *
 * @Date 2020/12/20 16:49
 * @Author 冷心影翼
 */
public class Problem74 {

	public static void main(String[] args) {
		Solution74 solution74 = new Solution74();
		int[][] matrix = new int[][] {
			{1,3,5,7},
			{10,11,16,20},
			{23,30,34,50},
		};
		System.out.println(solution74.searchMatrix(matrix, 11));
		System.out.println(solution74.searchMatrix2(matrix, 11));
	}

}

class Solution74 {
	public boolean searchMatrix(int[][] matrix, int target) {
		if(matrix.length == 0 || matrix[0].length == 0)
			return false;
		int l = 0;
		int r = matrix.length;
		int arrLength = matrix[0].length;
		while (l<r) {
			int mid = (l+r)/2;
			if(matrix[mid][0] <= target && matrix[mid][arrLength-1] >= target) {
				l = 0;
				r = arrLength;
				while (l<r) {
					int m = (l+r)/2;
					if(matrix[mid][m] == target) {
						return true;
					}
					if(matrix[mid][m] < target) {
						l = m+1;
					}else {
						r = m;
					}
				}
			}
			if(matrix[mid][0] > target) {
				r = mid;
			}
			if(matrix[mid][0] < target && matrix[mid][arrLength-1] < target) {
				l = mid+1;
			}
		}
		return false;
	}


	public boolean searchMatrix2(int[][] matrix, int target) {
		if(matrix.length == 0 || matrix[0].length == 0) {
			return false;
		}
		int l = 0;
		int r = matrix.length * matrix[0].length;
		while (l<r) {
			int mid = (l+r) / 2;
			int x = mid / matrix.length;
			int y = mid % matrix.length;
			if(matrix[x][y] == target)
				return true;
			if(matrix[x][y] < target) {
				l = mid+1;
			}else {
				r = mid;
			}
		}
		return false;
	}
}